package Leetcode.Stack;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @Author: kirito
 * @Date: 2024/4/19 12:50
 * @Description: .
 * 最大矩形
 * 困难
 * 相关标签
 * 相关企业
 * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
 * 输出：6
 * 解释：最大矩形如上图所示。
 * 示例 2：
 *
 * 输入：matrix = [["0"]]
 * 输出：0
 * 示例 3：
 *
 * 输入：matrix = [["1"]]
 * 输出：1
 *
 *
 * 提示：
 *
 * rows == matrix.length
 * cols == matrix[0].length
 * 1 <= row, cols <= 200
 * matrix[i][j] 为 '0' 或 '1'
 */

public class maximalRectangle {
    /**
     * 暴力
     * @param matrix
     * @return
     */
    public int maximalRectangle(char[][] matrix) {
        // 获取矩阵的行数
        int m = matrix.length;
        // 如果矩阵为空，则返回0
        if (m == 0) {
            return 0;
        }
        // 获取矩阵的列数
        int n = matrix[0].length;
        // 创建一个二维数组，用于存储每一行中'1'的左边第一个'1'的位置
        int[][] left = new int[m][n];

        // 填充left数组
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 如果当前元素是'1'
                if (matrix[i][j] == '1') {
                    // 如果j是0，则left[i][j]是0，因为左边没有'1'
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        // 初始化最大面积
        int ret = 0;
        // 遍历矩阵中的每个元素
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 如果当前元素是'0'，则跳过此元素
                if (matrix[i][j] == '0') {
                    continue;
                }
                // 计算当前'1'的宽度
                int width = left[i][j];
                // 初始化面积
                int area = width;
                // 从当前行的上一个行开始，向上遍历
                for (int k = i - 1; k >= 0; k--) {
                    // 更新宽度，取当前'1'和上一个行的'1'中较小的值
                    width = Math.min(width, left[k][j]);
                    // 更新面积，取当前面积和(i-k+1)乘以宽度的较大值
                    area = Math.max(area, (i - k + 1) * width);
                }
                // 更新最大面积
                ret = Math.max(ret, area);
            }
        }
        // 返回最大面积
        return ret;
    }

    public int maximalRectangle2(char[][] mat) {
        // 获取矩阵的行数和列数
        int n = mat.length, m = mat[0].length, ans = 0;
        // 创建一个二维数组用于存储每行的柱状图高度
        int[][] sum = new int[n + 10][m + 10];
        // 初始化sum数组，将每行的'0'设置为0，'1'设置为1
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = mat[i - 1][j - 1] == '0' ? 0 : sum[i - 1][j] + 1;
            }
        }
        // 创建两个数组，分别用于存储每列的左边和右边的边界
        int[] l = new int[m + 10], r = new int[m + 10];
        // 初始化左边和右边的边界为0和m+1
        Arrays.fill(l, 0);
        Arrays.fill(r, m + 1);
        // 使用栈来维护每列的单调递减序列
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            // 清空栈和左右边界数组
            Arrays.fill(l, 0);
            Arrays.fill(r, m + 1);
            d.clear();
            for (int j = 1; j <= m; j++) {
                // 如果栈不为空且当前高度小于栈顶高度，则更新右边界
                while (!d.isEmpty() && sum[i][d.peekLast()] > sum[i][j]) {
                    r[d.pollLast()] = j;
                }
                // 将当前列的索引加入栈中
                d.addLast(j);
            }
            // 清空栈
            d.clear();
            for (int j = m; j >= 1; j--) {
                // 如果栈不为空且当前高度小于栈顶高度，则更新左边界
                while (!d.isEmpty() && sum[i][d.peekLast()] > sum[i][j]) {
                    l[d.pollLast()] = j;
                }
                // 将当前列的索引加入栈中
                d.addLast(j);
            }
            // 遍历每列，计算以当前行结尾的矩形面积
            for (int j = 1; j <= m; j++) {
                ans = Math.max(ans, sum[i][j] * (r[j] - l[j] - 1));
            }
        }
        // 返回最大面积
        return ans;
    }

}
